#include <functional>
#include <iostream>
#include <memory>
#include <string>
#include <tuple>
#include <vector>


// --- 1. 基础 Monad 概念和 Identity Monad ---

// 代表一个 Monad 的概念（标记）
struct Monad
{
};

// Identity Monad: 最基础的 Monad
template <typename T>
struct Identity : Monad
{
    T value;
    explicit Identity(T v) : value(std::move(v)) {}
};

template <typename T>
auto unit_identity(T&& v)
{
    return Identity<std::decay_t<T>>(std::forward<T>(v));
}

template <typename T, typename Func>
auto bind(const Identity<T>& m, Func&& f)
{
    return f(m.value);
}

// --- 2. Writer Monad ---

template <typename LogType>
struct Monoid
{
    // 必须提供 empty 和 append 操作
    static LogType empty() { return LogType{}; }
    static LogType append(const LogType& a, const LogType& b)
    {
        if constexpr (std::is_same_v<LogType, std::string>)
        {
            return a + b;
        }
        else if constexpr (std::is_same_v<LogType, std::vector<typename LogType::value_type>>)
        {
            LogType res = a;
            res.insert(res.end(), b.begin(), b.end());
            return res;
        }
        else
        {
            // 对于其他类型，假设 += 和默认构造是 Monoid 操作
            LogType res = a;
            res.insert(res.end(), b.begin(), b.end());
            return res;
        }
    }
};

template <typename T, typename LogType>
struct Writer : Monad
{
    T value;
    LogType log;

    Writer(T v, LogType l) : value(std::move(v)), log(std::move(l)) {}

    // 便捷构造函数，用于返回没有日志的值
    explicit Writer(T v) : value(std::move(v)), log(Monoid<LogType>::empty()) {}
};

template <typename T, typename LogType>
auto unit_writer(T&& v)
{
    return Writer<std::decay_t<T>, LogType>(std::forward<T>(v));
}

template <typename T, typename LogType, typename Func, typename ReturnType = std::invoke_result_t<Func, T>>
auto bind(const Writer<T, LogType>& m, Func&& f) -> ReturnType
{
    static_assert(std::is_same_v<ReturnType, Writer<typename ReturnType::T, LogType>>, "Function must return a Writer with the same LogType");
    auto result = f(m.value);
    auto new_log = Monoid<LogType>::append(m.log, result.log);
    return Writer<typename ReturnType::T, LogType>(std::move(result.value), std::move(new_log));
}

template <typename LogType>
auto tell(const LogType& log)
{
    return Writer<std::monostate, LogType>(std::monostate{}, log);
}

// --- 3. Reader Monad ---

template <typename EnvType, typename T>
struct Reader : Monad
{
    using function_type = std::function<T(const EnvType&)>;
    function_type run;

    explicit Reader(function_type f) : run(std::move(f)) {}
};

template <typename EnvType, typename T>
auto unit_reader(T&& v)
{
    return Reader<EnvType, std::decay_t<T>>([v = std::forward<T>(v)](const EnvType&) { return v; });
}

template <typename EnvType, typename T, typename Func, typename ReturnType = std::invoke_result_t<Func, T>>
auto bind(const Reader<EnvType, T>& m, Func&& f) -> ReturnType
{
    return Reader<EnvType, typename ReturnType::T>(
        [m, f = std::forward<Func>(f)](const EnvType& env)
        {
            T val = m.run(env);
            return f(val).run(env);
        });
}

template <typename EnvType>
auto ask()
{
    return Reader<EnvType, EnvType>([](const EnvType& env) { return env; });
}

// --- 4. State Monad ---

template <typename StateType, typename T>
struct State : Monad
{
    using function_type = std::function<std::tuple<T, StateType>(const StateType&)>;
    function_type run;

    explicit State(function_type f) : run(std::move(f)) {}
};

template <typename StateType, typename T>
auto unit_state(T&& v)
{
    return State<StateType, std::decay_t<T>>([v = std::forward<T>(v)](const StateType& s) { return std::make_tuple(v, s); });
}

template <typename StateType, typename T, typename Func, typename ReturnType = std::invoke_result_t<Func, T>>
auto bind(const State<StateType, T>& m, Func&& f) -> ReturnType
{
    return State<StateType, typename ReturnType::T>(
        [m, f = std::forward<Func>(f)](const StateType& state)
        {
            auto [val, new_state] = m.run(state);
            return f(val).run(new_state);
        });
}

template <typename StateType>
auto get()
{
    return State<StateType, StateType>([](const StateType& s) { return std::make_tuple(s, s); });
}

template <typename StateType>
auto put(const StateType& new_state)
{
    return State<StateType, std::monostate>([new_state](const StateType&) { return std::make_tuple(std::monostate{}, new_state); });
}

// --- 5. Monad Transformers ---

// --- WriterT Transformer ---
template <template <typename...> class InnerMonad, typename LogType, typename T>
struct WriterT : Monad
{
    InnerMonad<std::tuple<T, LogType>> inner;

    explicit WriterT(InnerMonad<std::tuple<T, LogType>> i) : inner(std::move(i)) {}
};

template <template <typename...> class InnerMonad, typename LogType, typename T>
auto unit_writert(T&& v)
{
    return WriterT<InnerMonad, LogType, std::decay_t<T>>(unit_identity(std::make_tuple(std::forward<T>(v), Monoid<LogType>::empty()))
                                                         // 假设 InnerMonad 有从 Identity 构造的能力，或者我们直接用 Identity 作为示例
                                                         // 更通用的做法是要求 InnerMonad 有 unit 操作
    );
}

template <template <typename...> class InnerMonad, typename LogType, typename T, typename Func>
auto bind(const WriterT<InnerMonad, LogType, T>& m, Func&& f)
{
    // 这里为了简化，假设 InnerMonad 是 Identity
    // 一个完整的实现需要 InnerMonad 自身支持 bind
    auto [val, log] = m.inner.value;
    auto result_writer = f(val);  // f should return WriterT<InnerMonad, LogType, U>
    auto [new_val, new_log] = result_writer.inner.value;
    auto combined_log = Monoid<LogType>::append(log, new_log);
    return WriterT<InnerMonad, LogType, decltype(new_val)>(unit_identity(std::make_tuple(new_val, combined_log)));
}

template <template <typename...> class InnerMonad, typename LogType>
auto tellt(const LogType& log)
{
    return WriterT<InnerMonad, LogType, std::monostate>(unit_identity(std::make_tuple(std::monostate{}, log)));
}

// --- ReaderT Transformer ---
template <template <typename...> class InnerMonad, typename EnvType, typename T>
struct ReaderT : Monad
{
    using function_type = std::function<InnerMonad<T>(const EnvType&)>;
    function_type run;

    explicit ReaderT(function_type f) : run(std::move(f)) {}
};

template <template <typename...> class InnerMonad, typename EnvType, typename T>
auto unit_readert(T&& v)
{
    // Requires InnerMonad to have a unit function
    return ReaderT<InnerMonad, EnvType, std::decay_t<T>>(
        [v = std::forward<T>(v)](const EnvType&)
        {
            return unit_identity(v);  // Simplified, assumes InnerMonad is Identity-like for unit
        });
}

template <template <typename...> class InnerMonad, typename EnvType, typename T, typename Func>
auto bind(const ReaderT<InnerMonad, EnvType, T>& m, Func&& f)
{
    // Simplified bind assuming InnerMonad is Identity-like for its bind
    return ReaderT<InnerMonad, EnvType, typename std::invoke_result_t<Func, T>::T>(
        [m, f = std::forward<Func>(f)](const EnvType& env)
        {
            auto inner_m = m.run(env);
            // This bind call depends on InnerMonad's bind implementation
            // Simplified: assume we can extract value from Identity-like
            auto val = inner_m.value;
            auto result_readert = f(val);
            return result_readert.run(env);
        });
}

template <template <typename...> class InnerMonad, typename EnvType>
auto askt()
{
    return ReaderT<InnerMonad, EnvType, EnvType>(
        [](const EnvType& env)
        {
            return unit_identity(env);  // Simplified unit for InnerMonad
        });
}

// --- StateT Transformer ---
template <template <typename...> class InnerMonad, typename StateType, typename T>
struct StateT : Monad
{
    using function_type = std::function<InnerMonad<std::tuple<T, StateType>>(const StateType&)>;
    function_type run;

    explicit StateT(function_type f) : run(std::move(f)) {}
};

template <template <typename...> class InnerMonad, typename StateType, typename T>
auto unit_statet(T&& v)
{
    return StateT<InnerMonad, StateType, std::decay_t<T>>(
        [v = std::forward<T>(v)](const StateType& s)
        {
            return unit_identity(std::make_tuple(v, s));  // Simplified unit
        });
}

template <template <typename...> class InnerMonad, typename StateType, typename T, typename Func>
auto bind(const StateT<InnerMonad, StateType, T>& m, Func&& f)
{
    return StateT<InnerMonad, StateType, typename std::invoke_result_t<Func, T>::T>(
        [m, f = std::forward<Func>(f)](const StateType& state)
        {
            auto inner_m = m.run(state);
            // Simplified: extract from Identity-like
            auto [val, new_state] = inner_m.value;
            auto result_statet = f(val);
            return result_statet.run(new_state);
        });
}

template <template <typename...> class InnerMonad, typename StateType>
auto gett()
{
    return StateT<InnerMonad, StateType, StateType>(
        [](const StateType& s)
        {
            return unit_identity(std::make_tuple(s, s));  // Simplified unit
        });
}

template <template <typename...> class InnerMonad, typename StateType>
auto putt(const StateType& new_state)
{
    return StateT<InnerMonad, StateType, std::monostate>(
        [new_state](const StateType&)
        {
            return unit_identity(std::make_tuple(std::monostate{}, new_state));  // Simplified unit
        });
}
